package three;

public class A042 {

    int prev = Integer.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        if(root==null) return true;
        boolean l = isValidBST(root.left);
        if(!l) return false;

        if(root.val <= prev) return false; //根节点 大于 左边的结点
        prev = root.val;


        return isValidBST(root.right);

    }

    //遍历法，直接判断当前节点是否满足搜索二叉树的条件（下面的结点可能大于最上面的，所以需要加上范围）
    public boolean isValidBST2(TreeNode root) {
        return func(root,Long.MIN_VALUE,Long.MAX_VALUE);
    }

    public boolean func(TreeNode root,long lower,long upper) { //根、最小值、最大值
        if(root==null) return true;
        int tmp = root.val;

        if(!(root.val>lower && root.val < upper)) return false; //根节点，大于左边，小于右边

        return func(root.left,lower,tmp) && func(root.right,tmp,upper);
    }



}
